%Dowód NP-zupełności problemu
\begin{description}
\item[Twierdzenie.] Określenie, czy z danej planszy SameGame można usunąć wszystkie klocki jest problemem NP-zupełnym, jeśli plansza ta ma co najmniej dwie kolumny i co najmniej pięć kolorów.
\end{description}

Dowód zostanie przeprowadzony poprzez redukcję do problemu 3-Partition, który jest problemem NP-zupełnym. Dowód jego NP-zupełności znajduje się w \cite{partitionnp}

\begin{description}
\item[3-Partition problem.] Dany jest multizbiór $A=\{a_{1}, a_{2},\cdots, a_{n}\}$ $n = 3m$ całkowitych dodatnich liczb takich, że $\sum_{i=1}^n a_{i} = tm$ . Problemem jest ustalenie czy istnieje podział $A$ na $m$ podzbiorów zawierających dokładnie $3$ elementy z $A$, których suma wynosi $t$.
\end{description}

\section{Budowa}
Gra SameGame dla której wykażemy równoważność z problemem 3-Partition zostanie zbudowana z dwóch kolumn. Lewa z nich koduje zbiory $S_{1},\cdots, S_{m}$. Konkretna konstrukcja budowana od dołu składa się z:
\begin{enumerate}
\item bloku $3m$ naprzemiennie ułożonych kolejno białych i czarnych klocków
\item m-1 sekcji, każda odpowiadająca jednemu zbiorowi, zbudowanych z $4m-1$ naprzemiennie ułożonych klocków białych i czarnych oraz jednego klocka koloru czerwonego u góry
\item bloku  $4m^{2}t - 4mt + 2m + 1$ naprzemiennie ułożonych czarnych i białych klocków gdzie pierwszy klocek jest tego samego koloru jak przed ostatni klocek poprzedniego bloku
\end{enumerate}

Prawa natomiast zawiera bloki kodujące liczbę a z zbioru $A$ począwszy od dołu.
\begin{enumerate}
\item bloki kodujące liczby a z zbioru A o długości $4ma$ składające się z zielonych klocków rozdzielonych pojedynczym niebieskim klockiem, łączna liczba klocków wynosi $4m^{2}t + 3m - 1$
\item blok $m-1$ czerwonych klocków z których wszystkie są rozdzielone przez dwa klocki niebieskie, łączna liczba klocków w tym bloku wynosi $3m-5$
\end{enumerate}

\simpleImage{img/samegame1.png}{Poglądowa konstrukcja.}{300}

\section{Równoważność SameGame i 3-partition problem}
$S_{1}, \cdots , S_{m}$ - rozwiązanie 3-Partition problem, tzn. $S_{k} = \{a_{k}, b_{k}, c_{k}\}, \forall k \colon a_{k} + b_{k} + c_{k} = t$.
Następnie wykonujemy poniższe czynności dla każdego z zbiorów $S_{k}$:
\begin{enumerate}
	\item Usuwamy bloki zielonych klocków związanych kolejno z $a_{k}$, $b_{k}$,  $c_{k}$
	\item Usuwamy parę czerwonych klocków
	\item Usuwamy najniższy blok niebieskich klocków
\end{enumerate}
Etap pierwszy można zawsze wykonać ponieważ $a_{k} + b_{k} + c_{k} = t$. Wynika z tego, że suma usuniętych klocków wynosi $4mt$ czyli dokładnie tyle ile wynosi różnica wysokości między czerwonymi klockami. W związku z zniwelowaniem bloków dzielących czerwone klocki możemy wykonać kolejny krok. Dzięki usunięciu najniższego bloku klocków niebieskich uzyskujemy przesunięcie czerwonego klocka tak by był dokładnie $4mt$ klocków wyżej od odpowiedniego dla niego klocka w kolumnie lewej.
W ten sposób pozostały trzy zielone grupy które usuwamy co powoduje, niebieskie bloki je rozdzielające składają się na blok który również usuwamy. W ten sposób prawa kolumna nie zawiera już żadnych klocków a z prawej kolumny zostały usunięte wszystkie czerwone klocki a bez nich lewa kolumna również się redukuje do zera.
W powyższy sposób udowodniliśmy, że jeśli 3-Partition problem posiada rozwiązanie to odpowiadający mu problem SameGame również je posiada.

\section{Równoważonść SameGame i 3-partition problem - część 2}
Posłużymy się ponownie przedstawionym powyżej egzemplarzem problemu SameGame który jak wiemy posiada sekwencje ruchów która prowadzi do rozwiązania problemu.
Załóżmy, że istnieje rozwiązanie które usuwa czerwone klocki z lewej kolumny poza kolejnością. Oznacza to, że usuwamy czerwony klocek z lewej kolumny, gdy $4mt$ klocków powyżej znajduje się jeszcze inny czerwony klocek. Natomiast najwyżej położony czerwony klocek znajdujący się w prawej kolumnie nie możne znajdować się wyżej niż $3m-5$ pozycji wyżej. Oznacza to, że w lewej kolumnie istnieje czerwony klocek znajdujący się nad dowolnym czerwonym klockiem z prawej kolumny. W takiej sytuacji możemy jedynie obniżać pozycje klocków w prawej kolumnie bądź powodować obniżenie obu kolumn o 1 klocek. Powoduje to, że różnica wysokości pozostaje taka sama bądź się zwiększa, a więc czerwony klocek z lewej kolumny nie ma możliwości zostać usuniętym. Dowodzi to wymogu usuwania czerwonych klocków od góry w każdym poprawnym rozwiązaniu.
Po analizie przedstawionego problemu możemy dość do wniosku, że nie istnieje możliwość zmiany wysokości czerwonych klocków znajdujących się w lewej kolumnie co powoduje, że lewa kolumna jest zawsze rozwiązywana jako ostatnia a manipulacja na białych i czarnych klockach nie wpływa na poprawność rozwiązania.
Natomiast usunięcie separatora czerwonych klocków z prawej kolumny gdy rozdziela on w dalszym ciągu dwa czerwone klocki powoduje niemożność rozwiązania problemu. Spowoduje to połączenie dwóch czerwonych klocków a więc w następstwie zmuszenie nas do usunięcia ich razem a wobec braku możliwości regulowania wysokości czerwonych klocków w lewej kolumnie spowoduje to, że zawsze będzie usunięty co najwyżej jeden klocek z kolumny lewej a więcej niż jeden z prawej co spowoduje brak równowagi w ilości klocków czerwonych w lewej i prawej kolumnie.
Oznacza to, że jedynymi ruchami jakimi może zaczynać się poprawne rozwiązanie jest sposób przedstawiony w części pierwszej dowodu równoważności.

\section{Rozszerzenie na więcej kolumn/więcej kolorów}
Rozszerzenie problemy ogranicza się do wypełnienia dodatkowych miejsc na planszy kolorem białym lub czarnym bądź innym niewystępującym w dowodzie.

\section{Trudność problemu minimalizacji}
Jeśli posiadany algorytm rozwiązujący problem minimalizacji ilości pozostałych klocków dla danej planszy da rezultat $0$, to problem jest rozwiązywalny, a jeśli inna niż $0$ jest nierozwiązywalny. Więc algorytm ten rozwiązuje problem NP-zupełny więc problem minimalizacji również NP-zupełny.
